/*
 * =====================================================================================
 *
 *       Filename:  longest-subsequence.cpp
 *
 *    Description:
 *
 *        Version:  1.0
 *        Created:  2017年08月06日 13时05分08秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Crane (), wanghe@galaxyeye-tech.com
 *   Organization:  Galaxy-eye
 *
 * =====================================================================================
 */

#include <vector>
#include <string>
#include <iostream>

using namespace std;

// 矩阵中的一条记录/槽
struct  Record
{
    enum { kInitSize = 0 };

    int preRow;            // 回溯时: 上一个与当前槽关联的槽的行数
    int preCol;            // 回溯时: 上一个与当前槽关联的槽的列数
    int maxLen;         // 最长子序列/子串长度

    Record() {
        preRow = preCol = maxLen = kInitSize;
    }

    Record(int row, int col, int len) {
        preRow = row;
        preCol = col;
        maxLen = len;
    }

    void show() const {
        std::cout << preRow << ",";
        std::cout << preCol << ",";
        std::cout << maxLen << "";
        std::cout << "     ";
    }

    void SetLen(int len) {
        maxLen = len;
    }

    int GetLen() const {
        return maxLen;
    }

    void SetValue(int value) {
        SetLen(value);
    }

    int GetValue() const {
        return GetLen();
    }
};

template<class Containor>
void showContain(const  Containor & ins)
{
    for( auto ele : ins )
        std::cout << ele  << " ";
    std::cout << std::endl;
}

class SubLongestSubsequence
{
    typedef  vector<Record>     RecordRow;  // 一维矩阵, 一行槽
    typedef  vector<RecordRow>  Board;      // 二维矩阵

    Board    board_;
    int      colNum_;
    int      rowNum_;

public:
    void LongestSubsequence(string s1, string s2) {
        s1 = '0' + s1;
        s2 = '0' + s2;
        initBoard(s2.size(), s1.size());

        __LongestSubsequence(s1, s2);
    }

    // 顺序1对1匹配
    void LongestSubstring(string s1, string s2) {
        s1 = '0' + s1;
        s2 = '0' + s2;

        initBoard(s2.size(), s1.size());

        __LongestSubstring(s1, s2);
    }

    template<class Iterator>
    void Maximux_Subarray(Iterator first, Iterator last)
    {
        std::vector<int>  nums;
        nums.reserve(15);
        nums.push_back(0);

        std::copy(first, last, std::back_inserter(nums));
        initBoard(nums.size(), nums.size());

        showContain( nums );

        __Maximux_Subarray(nums);
    }


    void show() const {
        for ( const auto & row : board_ )
        {
            for ( const auto & slot : row )
            {
                slot.show();
            }

            std::cout << std::endl;
        }
        std::cout << std::endl;
    }

private:
    //int __LongestSubsequence(const string &s1, size_t len1, const string &s2, size_t  len2)
    int __LongestSubsequence(const string &s1, const string &s2)
    {
        //Record  max  = {0, 0, 0};

        for (size_t i = 1; i < s2.size(); i++)
        {
            for (size_t j = 1; j < s1.size(); j++)
            {
                // most important
                if ( s1[j] == s2[i] )
                {
                    board_[i][j].SetLen( 1 + board_[i-1][j-1].GetLen() );
                }
                else
                {
                    int preMax = std::max( board_[i][j-1].GetLen(),  board_[i-1][j].GetLen() );
                    board_[i][j].SetLen(preMax);
                }
            }
        }

        return 0;
    }

    int __LongestSubstring(string s1, string s2)
    {
        for (size_t i = 1; i < s2.size(); i++)
        {
            for (size_t j = 1; j < s1.size(); j++)
            {
                // most important
                if ( s1[j] == s2[i] )
                {
                    board_[i][j].SetLen( 1 + board_[i-1][j-1].GetLen() );
                }
                else
                {
                    board_[i][j].SetLen(0);
                }
            }
        }

        return 0;
    }

    void  __Maximux_Subarray(const std::vector<int> & nums)
    {
        int max = 0;

        for (size_t i = 1; i < nums.size(); i++)
        {
            for (size_t j = i; j < nums.size(); j++)
            {
                if ( i == j )
                    board_[i][j].SetValue(nums[j]);
                else
                    board_[i][j].SetValue(  nums[j] +
                                            board_[i][j-1].GetValue()
                                        );

                max = std::max( max, board_[i][j].GetValue() );
            }
        }

        std::cout << "max is: " << max << std::endl;

    }

    void initBoard(int rowNum, int colNum)
    {
        /*
         *      s1 = "abcd"
         *      s1 = "1234"
         *
         *       a b c d
         *     1
         *     2
         *     3
         *     4
         *
         */
        rowNum_ = rowNum;
        colNum_ = colNum;

        board_.resize(rowNum_);

        RecordRow  oneRow(colNum_);
        std::fill_n(board_.begin(), rowNum_, oneRow);
    }
};

#define  ArraySize(array)       ( sizeof(array) / sizeof( array[0] ) )

int main(int argc, char **argv)
{
    SubLongestSubsequence s1;
    //s1.LongestSubsequence("abcd", "b1d2");
    //s1.LongestSubsequence("ABCBDAB", "BDCABA");
    s1.LongestSubsequence("BDCABA", "ABCBDAB");
    s1.show();

    s1.LongestSubsequence("abcd", "b1d2");
    s1.show();

    s1.LongestSubstring("abcdeft", "bcd2defta");
    s1.show();

    s1.LongestSubstring("21232523311324", "312123223445");
    s1.show();

    //int  arrs[]= {1, -1, 3, -4 , 6, 8};
    int  arrs[]= {1, -2, 3, 10, -4, 7, 2, -5};
    s1.Maximux_Subarray(arrs, arrs + ArraySize(arrs) );
    s1.show();
}

